#include <Ape/Collections/Map.h>
#include <Ape/EIndexOutOfRange.h>

#include <Ape/MT/Mutex.h>

namespace Ape {
	namespace Collections {
		using Ape::MT::MutexLock;
		
		class MapImpl;
		
		struct MapNode {
			void* Key;
			void* Value;
			
			MapNode* Less;
			MapNode* More;
			
			MapNode* Up;
			
			static MapNode* create (void* K, void* V) {
				MapNode* node = new MapNode;
				node->Key = K;
				node->Value = V;
				node->Less = NULL;
				node->More = NULL;
				node->Up = NULL;
				
				return node;
			}
			
			MapNode* getFor (void* K, const MapImpl* map) {
				int cmp = map->CompareKeys (K, this->Key);
				// they're looking for us!
				if (!cmp)
					return this;
					
				// they're looking for someone else
				MapNode* nodeToLookIn = NULL;
				if (cmp == 1) {
					nodeToLookIn = this->More;
				}
				else { // if (cmp == -1)
					nodeToLookIn = this->Less;
				}
				if (!nodeToLookIn)
					throw Ape::EIndexOutOfRange (L"No such key");
				return nodeToLookIn->getFor (K, map);
			}
			/**
				@param node user deleted
				@param map map which we will ask to compare the Keys
			*/
			void pushChild (MapNode* node, const MapImpl* map) {
				int cmp = map->CompareKeys (node->Key, this->Key);
				
				//printf("cmp %i\n", cmp);
				
				if (!cmp) {
					//printf("eq\n");
					this->Value = node->Value;
				}
				else {
					MapNode** pushTo = NULL;
					if (cmp == 1) {
						pushTo = & (this->More);
					}
					else {
						pushTo = & (this->Less);
					}
					//printf("still OK\n");
					if (*pushTo) {
						(*pushTo)->pushChild (node, map);
					}
					else {
						MapNode* newBornChild = MapNode::create (node->Key, node->Value);
						newBornChild->Up = this;
						*pushTo = newBornChild;
					}
				}
			}
			void ExcludeFromTree (MapNode** pRoot, MapImpl* map) {
				MapNode*& root = *pRoot;
				//printf("root is [%p]\ni am [%p]\n", root, this);
				
				MapNode* orphan_1 = this->Less;
				MapNode* orphan_2 = this->More;
				
				if (orphan_1)
					orphan_1->Up = NULL;
				if (orphan_2)
					orphan_2->Up = NULL;
					
				//printf("orphan_1 [%p]\norphan_2 [%p]\n", orphan_1, orphan_2);
				
				this->Less = NULL;
				this->More = NULL;
				if (this->Up) {
					//printf("I have a parent - [%p]\n", this->Up);
					
					if (this->Up->Less == this)
						this->Up->Less = NULL;
					if (this->Up->More == this)
						this->Up->More = NULL;
					this->Up = NULL;
					if (orphan_1)
						root->pushChild (orphan_1, map);
					if (orphan_2)
						root->pushChild (orphan_2, map);
				}
				else {
					//printf("I have no parent\n");
					
					MapNode* newRoot = NULL;
					MapNode* somethingToPush = NULL;
					if (orphan_1) {
						//printf("first orphan will be the root\n");
						newRoot = orphan_1;
						somethingToPush = orphan_2;
					}
					else if (orphan_2) {
						//printf("second orphan will be the root\n");
						newRoot = orphan_2;
						somethingToPush = orphan_1;
					}
					//printf("assigning new root [%p]\n", newRoot);
					root = newRoot;
					
					if (somethingToPush) {
						//printf("there is something to push [%p]\n", somethingToPush);
						root->pushChild (somethingToPush, map);
					}
				}
			}
		};
		
		MapImpl::MapImpl()
				: m_RootNode (NULL)
		{
			InitObjectMutex();
		}
		
		MapImpl::~MapImpl() {}
		
		void MapImpl::set (void* K, void* V) {
			MutexLock lock (GetObjectMutex() );
			//printf("set\n");
			if (!m_RootNode) {
				//printf("empty root\n");
				m_RootNode = MapNode::create (K, V);
			}
			else {
				//printf("create node\n");
				MapNode* node = MapNode::create (K, V);
				//printf("push further\n");
				m_RootNode->pushChild (node, this);
				//printf("delete node\n");
				delete node;
			}
		}
		void* MapImpl::get (void* k) const {
			MutexLock lock (GetObjectMutex() );
			if (!m_RootNode)
				throw Ape::EIndexOutOfRange (L"No such key");
				
			return m_RootNode->getFor (k, this)->Value;
		}
		
		void MapImpl::remove (void* k) {
			MutexLock lock (GetObjectMutex() );
			//printf("remove\n");
			if (!m_RootNode) {
				//printf("no root node - nothing to remove\n");
				throw Ape::EIndexOutOfRange (L"no such node");
			}
			//printf("get node for the key\n");
			MapNode* node = m_RootNode->getFor (k, this);
			//printf("ok - node is [%p]\n", node);
			node->ExcludeFromTree (&m_RootNode, this);
			//printf("node excluded itself out of the tree\n", node);
			
			DisposeValues (node->Key, node->Value);
			delete node;
		}
		
		bool MapImpl::exists (void* K) {
			if (!m_RootNode)
				return false;
			try {
				m_RootNode->getFor (K, this);
				//printf("found\n");
				return true;
			}
			catch (Ape::EIndexOutOfRange& exc) {
				//printf("not found\n");
				return false;
			}
		}
		
		void MapImpl::dispose_node (MapNode* node) {
			if (!node)
				return;
			dispose_node (node->Less);
			node->Less = NULL;
			
			dispose_node (node->More);
			node->More = NULL;
			
			DisposeValues (node->Key, node->Value);
			delete node;
		}
		
		void MapImpl::remove_all() {
			MutexLock lock (GetObjectMutex() );
			MapNode* node = m_RootNode;
			m_RootNode = NULL; // from this moment we may be thread-safe
			dispose_node (node);
		}
	}
}

